from typing import *
from math import inf


class Solution:

    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        mp = [[inf] * n for _ in range(n)]
        for a, b, v in edges:
            mp[a][b] = mp[b][a] = v
        vis = [[False] * n for _ in range(n)]
        for i in range(n):
            vis[i][i] = True
            mp[i][i] = 0
            for _ in range(n - 1):
                p = -1
                for j in range(n):
                    if not vis[i][j] and (p == -1 or mp[i][j] < mp[i][p]):
                        p = j
                for j in range(n):
                    mp[i][j] = min(mp[i][j], mp[i][p] + mp[p][j])
                vis[i][p] = True
        ans = tot = inf
        for i in range(n):
            cnt = 0
            for j in range(n):
                if mp[i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= tot:
                tot = cnt
                ans = i
        return ans


s = Solution()
print(s.findTheCity(4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4))

print(
    s.findTheCity(
        5, [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]],
        2))
